/**
 * 描述：一次不止走一步。
 *
 * @author wangb
 * @version 1.0
 * create 2018-11-05-0:00
 */
public class LittleSoldierWithDifferentStep{
    public static final int N = 2;
    public static final int M = 2;



    public static int[][] result;

    /**
     * 记忆化搜索
     * @param n
     * @param m
     * @return
     */
    public static int solve(int n ,int m ){
        if(n == 0 || m == 0)
            return 1;

        if(n < 0 || m < 0)
            return 0;

        if(result[n][m] >= 0)
            return result[n][m];

        result[n][m] = solve (n -1,m) + solve (n ,m -1)
        +solve (n -2,m) + solve (n , m -2);
        return result[n][m];


    }

    /**
     * 迭代版本的。处理边界情况比较复杂。
     * @param n
     * @param m
     * @return
     */
    public static int solveDitui(int n ,int m){
        for ( int i = 0 ; i <= N  ; i++ ) {
            result[i][0] = 1;
        }
        for ( int i = 0 ; i <=M  ; i++ ) {
            result[0][i] = 1;
        }
        result[1][1] = result[0][1] + result[1][0];
        for ( int i = 2 ; i <=N  ; i++ ) {
            result[i][1] =result[i - 1][1] + result[i][0] + result[i - 2][1];
        }
        for ( int i = 2 ; i <=M  ; i++ ) {
            result[1][i] = result[1][i-1] + result[1][i -2] + result[0][i];
        }

        for ( int i = 2 ; i <=N  ; i++ ) {
            for ( int j = 2 ; j <=M  ; j++ ) {
                result[i][j] = result[i-1][j] + result[i][j-1] + result[i-2][j] + result[i][j-2];
            }
        }


        return result[n][m];
    }


    public static void main(String[] args){
        result = new int[N + 1][M + 1];
        for ( int i = 0 ; i <=N; i++ ) {
            for ( int j = 0 ; j <=M  ; j++ ) {
                result[i][j] = -1;
            }
        }

        int s = solve (N,M);
        System.out.println ("递归的结果：");
        System.out.println (s);
        s = solveDitui (N,M);
        System.out.println ("递推的结果：");
        System.out.println (s);
    }
}
